package com.kevin.Code.DP;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author Vinlee Xiao
 * @Classname RussianDollEnvelopes
 * @Description Leetcode 354. 俄罗斯套娃信封问题 难度 困难 动态规划
 * @Date 2021/10/3 17:27
 * @Version 1.0
 */
public class RussianDollEnvelopes {

    /**
     * 二维问题转换为一维问题
     *
     * @param envelopes
     * @return
     */
    public int maxEnvelopes(int[][] envelopes) {

        int len = envelopes.length;
        if (len == 1) {
            return 1;
        }

        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {

                if (o1[0] == o2[0]) {
                    return o2[1] - o1[1];
                }

                return o1[0] - o2[0];
            }
        });

        //问题就变成最长递增序列的问题 可以只考虑 h一个维度
        //二维降序是为了避免错误

        //明确dp的含义
        int dp[] = new int[len];
        dp[0] = 1;
        int result = Integer.MIN_VALUE;

        for (int i = 1; i < len; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {

                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }

        return result;
    }


    public static void main(String[] args) {
        RussianDollEnvelopes russianDollEnvelopes = new RussianDollEnvelopes();

        int[][] nums = new int[][]{{5, 4}, {6, 4}, {6, 7}, {2, 3}};

        int i = russianDollEnvelopes.maxEnvelopes(nums);
        System.out.println(i);
    }
}
